//
//  Problem1024.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/10.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1024. 视频拼接 【动态规划】【数组拼接】
 你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
 视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
 我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

 示例 1：
     输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
     输出：3
     解释：
     我们选中 [0,2], [8,10], [1,9] 这三个片段。
     然后，按下面的方案重制比赛片段：
     将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
     现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。
 示例 2：
     输入：clips = [[0,1],[1,2]], T = 5
     输出：-1
     解释：
     我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。
 示例 3：
     输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
     输出：3
     解释：
     我们选取片段 [0,4], [4,7] 和 [6,9] 。
 示例 4：
     输入：clips = [[0,4],[2,8]], T = 5
     输出：2
     解释：
     注意，你可能录制超过比赛结束时间的视频。
 提示：
     1 <= clips.length <= 100
     0 <= clips[i][0] <= clips[i][1] <= 100
     0 <= T <= 100
 */
@objcMembers class Problem1024: NSObject {
    func solution() {
        print(videoStitching([[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], 10))

        print(videoStitching([[0,1],[1,2]], 5))
        print(videoStitching([[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], 9))
        print(videoStitching([[0,4],[2,8]], 5))
        print(videoStitching([[3,6],[3,6],[0,4],[6,6],[8,10],[6,10],[0,1],[6,9]], 2))
    }
    
    /*
     动态规划
     1: 创建一个数组 dp[len]
     2: dp[i] clips[i]的第一个数到T需要裁剪的最小数目
     3: dp[i] = min()
        for(j in 0..<count) {
            if i != j  &&  clips[i][1] >= clips[j][0] && clips[i][1] < clips[j][1] {     // 满足条件的下一个数组
                if ==  {        // 这2个相等，不需要裁剪
                    dp[i] = dp[j]
                } else {
                    // 需要裁剪1次, 这里有2中情况
                    // 1: (0, 4) (3, 7) => 前面裁剪一次(1, 3)
                    // 2: (1, 4) (0, 5) => 后面裁剪一次(4, 5)
                    dp[i] = 1 + dp[j]
                }
            
            }
        }
     */
    func videoStitching(_ clips: [[Int]], _ T: Int) -> Int {
        if T == 0 {
            return 0
        }
        var dp = Array(repeating: 200, count: clips.count)
        
        var value = 200
        for i in 0..<clips.count {
            if clips[i][0] == 0 {
                value = min(value, videoStitchingDP(clips, T, &dp, i, clips[i][1]))
            }
        }
        return value == 200 ? -1 : value
    }
    
    func videoStitchingDP(_ clips: [[Int]], _ T: Int, _ dp: inout [Int], _ start: Int, _ startValue: Int) -> Int {
        if clips[start][0] >= T {       // 边界： (2,3) T=1
            dp[start] = -1
        } else if startValue >= T {     // 边界： (1,4) T=2
            dp[start] = 1
        }
        if dp[start] != 200 {
            return dp[start]
        }
        
        for i in 0..<clips.count {
            if i != start, clips[start][1] >= clips[i][0] && clips[start][1] < clips[i][1] {
                let value = videoStitchingDP(clips, T, &dp, i, clips[i][1])
                if value != -1 {
                    dp[start] = min(dp[start], 1 + value)
                }
            }
        }
        
        if dp[start] == -2 {
            if clips[start][1] >= T {
                dp[start] = 1
            } else {
                dp[start] = -1
            }
        }
        
        return dp[start]
    }
}
